Article 1316

Title of the article

ON SINGLE DIAGNOSTIC TESTS FOR LOGIC CIRCUITS IN THE ZHEGALKIN BASIS

Authors

Popkov Kirill Andreevich, Junior researcher, sector of theoretical cybernetics, department No. 4, Keldysh Institute of Applied Mathematics of the Russian Academy of Sciences (4 Miusskaya square, Moscow, Russia), kirill-formulist@mail.ru

Index UDK

519.718.7

DOI

10.21685/2072-3040-2016-3-1

Abstract

Background. The article considers a problem of synthesis of irredundant logic circuits in the basis {&, ,1, 0} which implement Boolean functions on n variables and allow short single diagnostic tests regarding constant faults of type 0 on outputs of gates. It relates to the problem of synthesis of easily testable circuits which was put in 1950s and has been well researched by now.
Materials and methods. For construction of easily testable circuits the earlier known method of synthesis was used and modified for the given problem. The lower bounds of test lengths were proved “by contradiction” via obtaining restrictions on the structure of circuits admitting short tests.
Results. For each Boolean function, the minimal possible length value of a single diagnostic test in the basis {&, ,1, 0} regarding the faults mentioned has been found. In particular, it is proved that this value does not exceed two.
Conclusions. The problem considered is completely solved. In particular, earlier upper bounds of the minimal lengths of single diagnostic tests in this problem statement have been significally improved.

Key words

logic circuit, fault, single diagnostic test.

Download PDF
References

1. Chegis I. A., Yablonskiy S. V. Trudy Matematicheskogo instituta imeni V. A. Steklova [Proceedings of Mathematical Institute named after V. A. Steklov]. 1958, vol. 51, pp. 270–360.
2. Yablonskiy S. V. Materialy Vsesoyuznogo seminara po diskretnoy matematike i ee prilozheniyam [Proceedings of All-USSR seminar on discrete mathematics and its applications]. Moscow: MGU, 1986, pp. 7–12.
3. Yablonskiy S. V. Matematicheskie voprosy kibernetiki [Problems of mathematical cybernetics]. Issue 1. Moscow: Nauka, 1988, pp. 5–25.
4. Red'kin N. P. Nadezhnost' i diagnostika skhem [Reliability and diagnostics of circuits]. Moscow: Izd-vo MGU, 1992.
5. Reddy S. M. IEEE Trans. Comput. 1972, vol. 21, no. 1, pp. 124–141.
6. Kolyada S. S. Verkhnie otsenki dliny proveryayushchikh testov dlya skhem iz funktsional'nykh elementov: dis. kand. fiz.-mat. nauk [Upper bounds of test lengths for circuits consisting of functional gates: dissertation to apply for the degree of the candidate of physical and mathematical sciences]. Moscow, 2013, 77 p.
7. Romanov D. S. Diskretnaya matematika [Discrete mathematics]. 2014, vol. 26, iss. 2, pp. 100–130.
8. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 1986, no. 1, pp. 72–74.
9. Red'kin N. P. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. Issue 2. Moscow: Nauka, 1989, pp. 198–222.
10. Romanov D. S. Diskretnaya matematika [Discrete mathematics]. 2013, vol. 25, iss. 2, pp. 104–120.
11. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 1988, no. 2, pp. 17–21.
12. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 1992, no. 5, pp. 43–46.
13. Borodina Yu. V. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2008, no. 5, pp. 49–52.
14. Popkov K. A. Preprinty IPM im. M. V. Keldysha [Preprints of Keldysh Institute of Applied Mathematics]. 2015, no. 74, 20 p.
15. Borodina Yu. V. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 2008, no. 1, pp. 40–44.
16. Borodina Yu. V., Borodin P. A. Diskretnaya matematika [Discrete mathematics]. 2010, vol. 22, iss. 3, pp. 127–133.
17. Ugol'nikov A. B. Klassy Posta: ucheb. posobie [Post’s classes: tutorial]. Moscow: Izd-vo TsPI pri mekhaniko-matematicheskom fakul'tete MGU, 2008.

 

Дата создания: 19.12.2016 11:13
Дата обновления: 19.12.2016 15:09